package com.data_structure_algorithm.data_structure.stack.operationstack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author 何章怀晓 hezhanghuaixiao
 * @version V1.0
 * @desc 逆波兰表达式
 */
public class PolandNotation {

  public static void main(String[] args) {
    Stack<Integer> numStack = new Stack<>();

    //将中缀表达式转为后缀表达式
    String midExp = "(3 + 4 )* 5 -6";

    String antiPolandExpression = infixToSuffix(midExp);

    String[] exp = antiPolandExpression.split(" ");

    List<String> antiPolandExpressionList = new ArrayList<>();

    for (String item : exp
    ) {
      antiPolandExpressionList.add(item);
    }

    for (int i = 0; i < antiPolandExpressionList.size(); i++) {
      //判断是否为多位数    \\d+多位数
      if (!antiPolandExpressionList.get(i).matches("\\d+")) {
        //符号
        //弹出两个数字和当前运算符运算
        Integer v1 = numStack.pop();
        Integer v2 = numStack.pop();

        //这里将运算符字符串转为字符，因为每个运算符是单独的
        char oper = antiPolandExpressionList.get(i).toCharArray()[0];

        int result = operation(v1, v2, oper);
        numStack.push(result);

      } else {
        //数字
        numStack.push(Integer.parseInt(antiPolandExpressionList.get(i)));
      }

    }

    //最后留在stack中的是结果
    System.out.println(numStack.pop());


  }

  //运算
  public static int operation(int v1, int v2, int ope) {
    switch (ope) {
      case '+':
        return v1 + v2;
      case '-':
        return v2 - v1;
      case '*':
        return v1 * v2;
      case '/':
        return v2 / v1;
    }
    return -1;
  }

  //----------------------------------------------------------工具类，将中缀转为后缀

  static String infixToSuffix(String expression) {
    //操作符的栈
    Stack<String> opStack = new Stack<>();
    //后缀表达式的线性表
    ArrayList<String> suffixList = new ArrayList<>();

    //格式化表达式
    expression = insertBlanks(expression);
    String[] tokens = expression.split(" ");
    for (String token : tokens) {
      //过滤空串
      if (token.length() == 0) {
        continue;
      }
      //判断操作符+ - * /
      if (isOperator(token)) {
                /*
                什么时候操作符进栈？
                1.如果栈为空
                2.如果栈顶是 (
                3.如果栈顶是操作符，且优先级比当前token小

                什么时候需要将栈顶操作符出栈？
                1.栈顶操作符的优先级 >= 当前token
                */
        while (true) {
          //循环过程
          if (opStack.isEmpty() || opStack.peek().equals("(")
              || priority(opStack.peek()) < priority(token)) {
            //当前操作符入栈
            opStack.push(token);

            break;

          }
          //栈顶操作符的优先级 >= 当前token
          suffixList.add(opStack.pop());

        }
      } else if (token.equals("(")) {
        //左括号直接入栈
        opStack.push(token);

      } else if (token.equals(")")) {
        //如果有括号，循环弹操作符栈，放入list中，直到弹出左括号
        while (!opStack.peek().equals("(")) {

          suffixList.add(opStack.pop());

        }
        //重要，将最后的（弹出，此循环目的是消除小括号
        opStack.pop();

      } else if (isNumber(token)) { //数字直接入栈（此处为集合）

        suffixList.add(token);

      } else {

        throw new IllegalArgumentException("wrong char :" + expression);

      }
    }
    //如果表达式扫描完毕，操作符栈仍有数据，依次弹栈，压入list（逻辑栈）
    while (!opStack.isEmpty()) {

      suffixList.add(opStack.pop());

    }
    //到这里，逆波兰表达式已经在suffixList中了

    //将数字元素和操作符元素进行拼接
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < suffixList.size(); i++) {
      sb.append(suffixList.get(i));
      sb.append(' ');
    }
    return sb.toString();
  }

  //优先级比较
  private static int priority(String token) {
    if (token.equals("+") || token.equals("-")) {
      return 0;
    }
    if (token.equals("*") || token.equals("/")) {
      return 1;
    }
    return -1;
  }

  private static boolean isNumber(String token) {

    return token.matches("\\d+");
  }


  //操作符判断
  private static boolean isOperator(String token) {
    return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
  }

  //对原表达式进行格式化处理 给所有的非数字字符两边添加空格
  private static String insertBlanks(String expression) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < expression.length(); i++) {
      char c = expression.charAt(i);
      if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
        sb.append(' ');
        sb.append(c);
        sb.append(' ');
      } else {
        sb.append(c);
      }
    }
    return sb.toString();
  }

}
